UVa/11111 - Generalized Matrioshkas/matri.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <stack>
   4 #include <sstream>
   5
   6 using namespace std;
   7
   8 typedef long long ll;
   9
  10 //Verdadero si las sumas internas de [start, end] están correctas.
  11 bool todo_bien(int start, int end, const vector<ll> &v, const vector<int> &jmp){
  12
  13   int i = start+1;
  14   ll sum = 0;
  15   while (i < end){
  16     sum += -v[i];
  17     if (todo_bien(i, jmp[i], v, jmp) == false) return false;
  18     i = jmp[i]+1;
  19   }
  20
  21   //cout << "Todo_bien entre " << start << " , " << end << ", sum = " << sum << " ans = " << (sum < v[end]) << endl;
  22   return (sum < v[end]);
  23 }
  24
  25 int main(){
  26   string line;
  27   while (getline(cin, line)){
  28     vector<ll> v;
  29     stack<pair<ll, int> > stk;
  30     vector<int> jmp;
  31
  32     int i = 0;
  33     stringstream sin(line);
  34     ll x;
  35     bool bad = false;
  36     while (sin >> x){
  37       v.push_back(x);
  38       jmp.push_back(-1);
  39       if (x < 0){
  40         stk.push(make_pair(x, i));
  41       }else{
  42         if (stk.size() == 0) bad = true;
  43         else{
  44           ll y = stk.top().first;
  45           int j = stk.top().second;
  46           stk.pop();
  47           if (x == -y){
  48             jmp[i] = j;
  49             jmp[j] = i;
  50           }else bad = true;
  51         }
  52       }
  53       ++i;
  54     }
  55     if (stk.size()) bad = true;
  56     if (bad || !todo_bien(0, i-1, v, jmp)) cout << ":-( Try again." << endl;
  57     else cout << ":-) Matrioshka!" << endl;
  58   }
  59   return 0;
  60 }